#include "bigint.h"

big_int::big_int(int a)
{
   digits.push_back(a);
}

big_int::big_int(std::vector<int> va)
{
   digits = va;
}

big_int::big_int(std::string sa)
{
   if (sa.length() == 0)
   {
      digits.push_back(0);
      return;
   }
   for (int i = sa.length(); i >= BASE_LENGTH; i-=BASE_LENGTH)
   {
      digits.push_back(atoi(sa.substr(i - BASE_LENGTH, BASE_LENGTH).c_str()));
   }
   int k = sa.length() % BASE_LENGTH;
   if (k > 0)
   {
      digits.push_back(atoi(sa.substr(0,sa.length() % BASE_LENGTH).c_str()));
   }
}

std::pair<big_int,big_int> big_int::divide(const big_int& b)
{
   
   big_int a = *this;
   int shift = a.length()-b.length();
   std::vector<int> quot;
   while (shift >= 0)
   {
      int div = a.find_divisor(b, shift);
      quot.push_back(div);
      a = a.subtract(b.multiply(div),shift);
      shift--;
   }
   std::reverse(quot.begin(),quot.end());
   std::pair<big_int,big_int> result(quot,a);
   result.first.delete_zeros();
   return result;
}

big_int big_int::subtract(const big_int& b, int shift)
{
   if (compare_to(b,shift) < 0)
   {
      return *this;
   }
   big_int result = *this;
   int carry = 0;
   for (size_t i = 0; i < b.length(); i++)
   {  
      if (result.digits[i + shift] - b.digits[i] - carry < 0)
      {
         result.digits[i + shift] = result.digits[i + shift] + BASE - b.digits[i] - carry;
         carry = 1;
         continue;
      }
      result.digits[i + shift] = result.digits[i + shift] - b.digits[i] - carry;
      carry = 0;
   }
   for (size_t i = b.length() + shift; i < length(); i++)
   {
      if (result.digits[i] - carry < 0)
      {
         result.digits[i] = result.digits[i] + BASE - carry;
         carry = 1;
         continue;
      }
      result.digits[i] = result.digits[i] - carry;
      carry = 0;
   }
   result.delete_zeros();
   return result;
}

big_int big_int::multiply(int b) const
{
   big_int result = *this;
   int carry = 0;
   long long long_b = static_cast<long long>(b);
   for (size_t i = 0; i < length(); i++)
   {
      long long mult = long_b * digits[i] + carry;
      result.digits[i] = mult % BASE;
      carry = static_cast<int>(mult / BASE);
   }
   if (carry != 0)
   {
      result.digits.push_back(carry);
   }
   result.delete_zeros();
   return result;
}

int big_int::find_divisor(const big_int& b, int shift = 0)
{
   int l = 0;
   int r = BASE - 1;
   while (r - l > 0)
   {
       int m = (l + r + 1) / 2;
       if (compare_to(b.multiply(m), shift) < 0)
       {
           r = m - 1;
       }
       else
       {
           l = m;
       }
   }
   return l;
}

size_t big_int::length() const
{
   return digits.size();
}

int big_int::compare_to(const big_int& b, int shift = 0)
{  
   if (length() != b.length() + shift)
   {
      return length() - b.length() - shift;
   }
   for (int i = b.length() - 1; i >= 0; i--)
   {
      if (digits[i+shift] != b.digits[i]){
         return digits[i+shift] - b.digits[i];
      }
   }
   return 0;
}

void big_int::delete_zeros()
{
   size_t new_size = digits.size();
   while (new_size > 0 && !digits[new_size-1])
   {
      new_size--;
   }
   digits.resize(new_size);
}

std::string big_int::to_string()
{
   std::string ret = "";
   int digit;
   if (digits.size() == 0 || (digit = digits.back()) == 0)
   {
      return "0";
   }
   while (digit > 0)
   {
      ret += (digit % 10 +'0');
      digit /= 10;
   }
   std::reverse(ret.begin(),ret.end());

   for(int i = digits.size() - 2;i >= 0;i--)
   {
      int digit = digits[i];
      for (int j = BASE / 10; j > 0; j /= 10)
      {
         ret += ((digit / j) + '0');
         digit %= j;
      }
   }
   return ret;
}